// 读了最大的堆的概念
// 尝试编写最大堆
// 第一步：编写一个最大堆，然后，实现堆的使用。
// 使用方式便是堆排序的使用。

package main

import (
	"errors"
	"fmt"
)

// 定义最大堆的结构体
type maxheap struct {
	cap   int   // 容量
	count int   // 个数
	val   []int // 值
}

// golang 不支持重载的处理方式

// 数组初始化
func (m *maxheap) initMaxheap(val []int) {
	if val == nil {
		errors.New("val is nil")
	}
	m.val = append(m.val, 0)
	m.val = append(m.val, val...)
	m.count = len(m.val)
	m.buildUp()
	return
}

// 调整整个堆的节点的结构，是它符合最大堆的组成使用形式；
func (m *maxheap) buildUp() {
	for i := len(m.val) - 1; i > 0; i-- {
		for j := i; j > 0 && j/2 > 0 && m.val[i] > m.val[i/2]; j = j / 2 {
			m.swap(j, j/2)
		}
	}
}

func (m *maxheap) swap(indx1 int, indx2 int) {
	tempVal := m.val[indx1]
	m.val[indx1] = m.val[indx2]
	m.val[indx2] = tempVal
}
func (m *maxheap) insert(val int) {
	m.val = append(m.val, val)
	m.count = len(m.val) - 1
	for j := m.count; j > 0 && j/2 > 0 && m.val[j] > m.val[j/2]; j = j / 2 { // 上浮的格式的语法实现模板
		m.swap(j, j/2)
	}
}

// 删除堆顶元素
func (m *maxheap) remove() int {
	if m.count == 0 {
		errors.New("heap is empty")
	}
	temp := m.val[1]
	m.val = append(m.val[:1], m.val[2:]...) // 删除中间元素的方式
	m.val[1] = temp
	m.heapDown(1)
	m.count = len(m.val)
	return temp
}

// 不断地遍历一直到满足条件的为止
func (m *maxheap) heapDown(indx int) {
	for true {
		maxPos := indx
		if maxPos < len(m.val) && m.val[maxPos] < m.val[indx*2] {
			maxPos = indx * 2
		}
		if indx*2+1 < len(m.val) && m.val[maxPos] < m.val[indx*2+1] {
			maxPos = indx*2 + 1
		}
		if maxPos == indx {
			break
		}
		indx = maxPos
	}
}
// 删除的



func main() {

	nums := []int{12, 6, 4, 9, 1, 5, 14, 3}
	mh := new(maxheap)
	mh.initMaxheap(nums)
	fmt.Println(mh.val)
	mh.insert(20)
	fmt.Println(mh.val)
	mh.remove()
	fmt.Println(mh.val)

}
